1. Field of the Invention
This invention relates in general to a system and method for compression of data points having at least two coordinates, and more particularly to data in vector or raster format, and to a method for smoothing and compression of polyline data.
2. Background Information
Clustering algorithms have been developed in support of various disciplines, including biology (e.g., clustering bacterial growth), physics (e.g., clustering high-energy particles), demographics (e.g., clustering populations), medicine (e.g., identifying clusters of tumors), and information technology (e.g., data mining, compression, and sorting; image classification, segmentation, and retrieval).
Some aspects of clustering are described in: Barnard, J. M., “Agglomerative hierarchical clustering package from Barnard Chemical Information, Ltd.”, Daylight EUROMUG Meeting, Basel, Switzerland (1996); Can, F. and Ozkarahan, E. A., “Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases”, ACM TODS 15(4): 483-512 (December 1990); Cormen, T. H., Leiserson, C. E., and Rivest, R. L., “Introduction to Algorithms”, Second Edition, MIT Press and McGraw-Hill, Cambridge, Mass. (2001); Day, W. H. E. and H. Edelsbrunner, “Efficient algorithms for agglomerative hierarchical clustering methods”, Journal of Classification, 1(1), pp. 7-24 (1984); Downs, G., “Clustering in chemistry”, MathFIT workshop, Belfast (2001); Downs, G. M. and J. M. Barnard, “Clustering methods and their uses in computational chemistry”, Reviews in Computational Chemistry, Vol. 18, Ch. 1, pp. 5-40 (2003); U.S. Pat. No. 6,218,965 B1 to Gendron, M. L., Wischow, P. B., Trenchard, M. E., Lohrenz, M. C., Riedlinger L. M., and Mehaffey, M. J., “Moving Map Composer”, Halkidi, M., Batistakis Y., and Vazirgiannis, M., “Cluster validity methods: Part II”, SIGMOD Record (2002); Hartigan, J. A., “Clustering Algorithms”, John Wiley and Sons, Inc., New York, N.Y. (1975); Hartigan, J. A. and Wong, M. A., “A K-means clustering algorithm”, Applied Statistics, Vol. 28, 100-108 (1979); Ho, T. K. and Nagy G., “OCR with no shape training”, Proceedings of the 15th International Conference on Pattern Recognition, pp. 27-30, Barcelona, Spain, 2000; Hobby, J. and T. K. Ho, “Enhancing degraded document images via bitmap clustering and averaging”, Proceedings of the 4th International Conference on Document Analysis and Recognition, pp. 394-400, Ulm, Germany, (1997); Hoppner, F., Klawonn, F., Kruse R., and Runkler, T., “Fuzzy Cluster Analysis”, John Wiley and Sons, Inc., Chicester, England, (1999); Jain, A. K., M. N. Murty, and P. J. Flynn, “Data clustering: a review”, ACM Computing Surveys, Vol. 31, Issue 3, pp. 264-323 (1999); JMPIN V.4.0.4 statistical analysis software package, SAS Institute Inc., Cary, N.C. (2003); Layne, G., M. Gendron and M. Lohrenz, “POS Polyline Smoothing: Reduction of Polyline Vertices”, Proceedings of the Tenth International Conference on Industry, Engineering and Management Systems, Cocoa Beach, Fla., March, 2004; Sibson, R., “SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method”, Comput. J. 16(1): 30-34(1973); Spiegel, M. R., “Schaum's outline of theory and problems of probability and statistics”, Schaum's outline series, McGraw-Hill, New York, N.Y. (1975); Voorhees, E. M. “The effectiveness and efficiency of agglomerative hierarchic clustering in Document Retrieval”, Ph.D. Thesis, Cornell University, N.Y. (1985a); Voorhees, E. M., “The cluster hypothesis revisited”, Proceedings of the 8th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 188-196 (1985); and Yoon, J. P., Raghavan, V., and Chakilam, V., “BitCube: a three-dimensional bitmap indexing for XML documents”, Journal of Intelligent Information Systems, 17:241-252 (2001).
U.S. patent application Publication No. 20040233197 to Liu et al. discloses a method for data compression for reducing the complexity of lines representing handwriting. Curve smoothing for lines CAD generated lines is disclosed in U.S. patent application Publication No. 20030025697 to Gupta.